package primary.primary0;

import java.util.*;

/**
 *
 *
 * 在内容相同情况下，String会hash得到相同的key，由于char[]特殊机制，相同内容的在hash后值不会相同。
 */
public class S0049字母异位词分组 {


    /**
     * 82,感觉直接用排序后的当key就行
     */
    class Solution4 {
        public List<List<String>> groupAnagrams(String[] strs) {
            Map<String, List<String>> record = new HashMap<>();
            for(String s : strs){
                String sortedS = getSortedString(s);
                List<String> stringList = record.getOrDefault(sortedS, new ArrayList<>());
                stringList.add(s);
                record.put(sortedS, stringList);
            }
            List<List<String>> res = new ArrayList<>();
            for(Map.Entry<String, List<String>> entry: record.entrySet()){
                res.add(entry.getValue());
            }
            return res;
        }
        private String getSortedString(String s){
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            return new String(charArray);
        }
    }


    /**
     * 没搞懂，排序后哈希，但是两个不同的String，hash之后不是也有可能得到相同的hashCode吗?
     * 那么我得重写hashCode()方法才行?用equals来代替?
     * 或者自己写一个生成hashcode的方法，比如 数每个字母的个数，然后toString，那么还是会有不同的String.hashCode之后相同的问题。
     */
    class Solution3 {

    }

    /**
     * 16,5 差不多。。
     * 简化，Arrays.sort()方法，以及new String(xxxArray) 实现 String -> array -> sort -> String的转换
     */
    class Solution2 {
        /**
         * 11， 5
         * 符合这种规则的特征大概就是sort之后完全相同吧。
         * 主要考察String api的使用，以及怎么在处理sort之后的字符串的同时，保留原始字符串信息
         * 这样，先把每个字符串的sort结果拼在自己前面，然后对处理后得到的List进行list范围的sort
         */
        public List<List<String>> groupAnagrams(String[] strs) {
            if(strs.length == 0){
                return new ArrayList<>();
            }
            List<String> tempList1 = new ArrayList<>();
            for(int i = 0; i < strs.length; i++){
                char[] chars = strs[i].toCharArray();
                Arrays.sort(chars);
                tempList1.add(new String(chars) + strs[i]);
            }
            Collections.sort(tempList1);

            String template = null;
            List<List<String>> res = new ArrayList<>();
            List<String> curList = new ArrayList<>();
            for (String s : tempList1) {
                // 这里subString是包括前面不包括后面的
                if(s.substring(0, s.length()/2).equals(template)){
                    curList.add(s.substring(s.length() / 2));
                }else{
                    template = s.substring(0, s.length()/2);
                    curList = new ArrayList<>();
                    res.add(curList);
                    curList.add(s.substring(s.length()/2));
                }
            }
            return res;
        }
    }

    class Solution {
        /**
         * 11， 5
         * 符合这种规则的特征大概就是sort之后完全相同吧。
         * 主要考察String api的使用，以及怎么在处理sort之后的字符串的同时，保留原始字符串信息
         * 这样，先把每个字符串的sort结果拼在自己前面，然后对处理后得到的List进行list范围的sort
         */
        public List<List<String>> groupAnagrams(String[] strs) {
            if(strs.length == 0){
                return new ArrayList<>();
            }
            List<String> tempList1 = new ArrayList<>();
            for(int i = 0; i < strs.length; i++){
                List<Character> stringToList = stringToList(strs[i]);
                // 注意这个sort返回的是null，并不是返回sort之后的结果
                Collections.sort(stringToList);
                tempList1.add(listToString(stringToList) + strs[i]);
            }
            Collections.sort(tempList1);

            String template = null;
            List<List<String>> res = new ArrayList<>();
            List<String> curList = new ArrayList<>();
            for (String s : tempList1) {
                // 这里subString是包括前面不包括后面的
                if(s.substring(0, s.length()/2).equals(template)){
                    curList.add(s.substring(s.length() / 2));
                }else{
                    template = s.substring(0, s.length()/2);
                    curList = new ArrayList<>();
                    res.add(curList);
                    curList.add(s.substring(s.length()/2));
                }
            }
            return res;
        }

        public List<Character> stringToList(String inputString){
            char[] inputArray = inputString.toCharArray();
            List<Character> resList = new ArrayList<>();
            for (char c : inputArray) {
                resList.add(c);
            }
            return resList;
        }
        // mark: stringBuilder还是要注意使用
        public String listToString(List<Character> input){
            StringBuilder res = new StringBuilder();
            for (Character character : input) {
                res.append(character);
            }
            return res.toString();
        }
    }

}
